Over the past several years many methods and tools have been developed to improve application performance. Many of these methods and tools are based on using data reordering/placement algorithms to improve the application's data locality.
“Cache-Conscious Data Placement”, by Calder et al., the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, Calif., 1998, and incorporated herein by reference, presents a method to improve a program's locality using data placement. Calder et al discuss the use of all data variables types: global, local (stack), and dynamic (heap) variables, as well as constants.
The data reordering of Calder et al. is based on two kinds of feedback profiles. The first profile lists each object encountered during execution, the object's name, reference count, size and lifetime information. The second profile is a temporal relationship graph (TRG) between different variables accessed by the application. The nodes of the TRG graph are variables, while an edge between two variables provides an estimation of the number of cache conflicts that would arise if these two variables were overlapped in the same cache line.
U.S. Pat. No. 5,850,549, “Global Variable Coalescing”, to Blainey, et. al., assigned to the assignee of the present patent application and incorporated herein by reference, describes a weighted interference graph where each node represents a variable and each edge represents an access relationship between two variables. The weights on the edges represent the access frequency and the weights on the nodes represent the variable size.
However, these prior art data reordering optimization techniques do not go far enough; they do not realize the additional optimization opportunities revealed as a result of the data reordering. Therefore, there still exists a need to provide method and apparatus to exploit the opportunities revealed as a result of data reordering, and thus, to provide even greater application performance improvements.